package 力扣._00周赛._116双周赛.问题3;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Solution {
    public int lengthOfLongestSubsequence(List<Integer> nums, int target) {
        //装满背包0/1的最多物品
        int[] dp = new int[target + 1]; //最大物品, 为0表示无法刚好装满
        //初始化
        Arrays.fill(dp, -1);
        dp[0]=0;

        for (int i = 0; i < nums.size(); i++) {
            for (int j = target; j >= nums.get(i); j--) {
                if (dp[j - nums.get(i)] != -1) {
                    dp[j] = Math.max(dp[j], dp[j - nums.get(i)] + 1);
                }
            }
            System.out.println(Arrays.toString(dp));
        }
        return dp[target];
//

    }

    public static void main(String[] args) {
        List<Integer> nums = new LinkedList<>();
        nums.add(14);
        nums.add(6);
        nums.add(4);
        nums.add(15);
        nums.add(3);
        nums.add(6);
        nums.add(7);
        nums.add(8);
        int i = new Solution().lengthOfLongestSubsequence(nums, 36);
    }
}
